//
// Created by daiyizheng on 2022/3/27.
//
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//DFS

void dfs(TreeNode* node, unordered_map<int, TreeNode*> &map){
    if (!node) return;
    if(node->left)map.insert(make_pair(node->left->val, node));
    if(node->right)map.insert(make_pair(node->right->val, node));

    dfs(node->left, map);
    dfs(node->right, map);
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return nullptr;
    if (root == p || root == q) return root;
    //维护子节点与父亲节点的关系
    unordered_map<int, TreeNode*> map;
    dfs(root, map);

    //从节点p开始，依次访问它的祖先
    unordered_set<int> visited;
    while (p){
        visited.insert(p->val);
         p = map[p->val];

    }

    //从节点q开始，依次访问它的祖先
    while (q){
        if (visited.count(q->val)) return q;
        q = map[q->val];
    }
    return nullptr;
}

//后续遍历
TreeNode* lowestCommonAncestor1(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root== nullptr)return nullptr;
    if (root == p || root == q) return root;

    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);

    if (left == nullptr) return right;
    if (right == nullptr) return left;
    return root;

}